<?php
/**
 * @title 1505. 最多 K 次交换相邻数位后得到的最小整数 - 迭代
 * @author start2004
 */

class Solution {

    /**
     * @param String $num
     * @param Integer $k
     * @return String
     */
    function minInteger($num, $k) {
        /**
         * @since 2020-07-15 前半段
         */
        $prefixs = [];

        /**
         * @since 2020-07-15 长度
         */
        $len = strlen($num);
        if($len == 0){
            return false;
        } else {}

        /**
         * @since 2020-07-15 哈希
         */
        $hashs = array_fill(0, 10, []);
        $hashs[$num[0]][] = [0,0];

        /**
         * @since 2020-07-15 是否升序
         */
        $asc = true;

        /**
         * @since 2020-07-15 检查是否升序, 数字位置
         */
        for($i=1; $i<$len; $i++){
            /**
             * @since 2020-07-15 非升序
             */
            if($num[$i]<$num[$i-1]){
                $asc = false;
            } else {}

            /**
             * @since 2020-07-15 要移动的次数
             */
            $move = 0;
            for ($j=9; $j>$num[$i]; $j--){
                $move += count($hashs[$j]);
            }

            /**
             * @since 2020-07-15 数字位置, 移动次数
             */
            $hashs[$num[$i]][] = [$i, $move];
        }
        // return $hashs;

        /**
         * @since 2020-07-15 升序直接返回
         */
        if($asc){
            return $num;
        } else {}

        /**
         * @since 2020-07-15 数字从小到大, 9移动始终是0
         */
        $maxPosition = $len;
        for ($i=0; $i<9; $i++){
            if(isset($hashs[$i])){
                foreach ($hashs[$i] as list($position, $move)){
                    // if($move>0 AND $position<$maxPosition){
                    if($position<$maxPosition){
                        /**
                         * @since 2020-07-15 移动次数不够
                         */
                        if($k<$move){
                            $maxPosition = $position;
                            break;
                        } else {
                            $k -= $move;
                            $prefixs[] = $i;
                            // unset($num[$position]);
                            $num[$position] = " ";
                        }
                    } else {}
                }
            } else {}

            /**
             * @since 2020-07-15 break
             */
            if($k == 0){
                break;
            } else {}
        }
        // return [$prefixs, $num];

        /**
         * @since 2020-07-15 收官k>0
         *
         * 1. num升序队列过多, 导致小数字, 移动次数不够
         * 2. num已经是升序, 不需要移动
         */
        $num = str_replace(" ", "", $num);
        $result = implode("", $prefixs) . $num;
        if($k>0 AND $num){
            for ($i=strlen($result)-strlen($num); $i<strlen($result); $i++){
                if($result[$i] < $result[$i-1]){
                    /**
                     * @since 2020-07-15 迁移k位交换
                     */
                    for($j=1; $j<=$k AND $i>=1; $j++, $i--){
                        list($result[$i-1], $result[$i]) = [$result[$i], $result[$i-1]];
                    }
                    break;
                } else {}
            }
        } else {}

        /**
         * @return
         */
        return $result;
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.15.php
 */
$datas = [
    ["6673", 2],
    // ["66734735310005051622492887188185749505275129252273007816637627033869776847476632559216710454753", 63], // 00001163674735355622492887188185749505275129252273007816637627033869776847476632559216710454753
    // ["77984", 1],
    // ["2941", 1],
    // ["554", 1],
    // ["55456497803213206850845",10], // 05455649783213206850845
    // ["294984148179",11], // 124498948179
    // ["",4],
    // ["1",123],
    // ["4321",4,],
    // ["100",1],
    // ["36789",1000],
    // ["22",22],
    // ["9438957234785635408",23],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->minInteger($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
